{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "ae015f9d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The max sub array is [18, 20, -7, 12] and the max sum is 43\n"
     ]
    }
   ],
   "source": [
    "## 分而治之算法：求取最大子数组\n",
    "from typing import List\n",
    "from sys import maxsize\n",
    "\n",
    "\n",
    "def find_max_crossing_subarray(array: List, mid: int) -> tuple:\n",
    "    \" Find the largest array spanning the left and right parts, that is, the third case \"\n",
    "    i = mid\n",
    "    j = mid + 1\n",
    "    sum_now = 0\n",
    "    max_sum = -maxsize -1\n",
    "\n",
    "    while i >= 0:\n",
    "        sum_now += array[i]\n",
    "        if sum_now > max_sum:\n",
    "            left = i\n",
    "            max_sum = sum_now\n",
    "        i -= 1\n",
    "    left_max = max_sum\n",
    "       \n",
    "    sum_now = 0\n",
    "    max_sum = -maxsize - 1\n",
    "    while j < len(array):\n",
    "       sum_now += array[j]\n",
    "       if sum_now > max_sum:\n",
    "           right = j\n",
    "           max_sum = sum_now\n",
    "       j += 1\n",
    "    right_max = max_sum\n",
    "       \n",
    "\n",
    "    return array[left:right+1], left_max + right_max\n",
    "\n",
    "def find_max_subarray(array: List) -> tuple:\n",
    "    if len(array) <= 1:\n",
    "        return array, array[0]\n",
    "    \n",
    "    left_part = array[0:int(len(array)/2)]\n",
    "    right_part = array[int(len(array)/2):len(array)]\n",
    "\n",
    "    left_sub_array, left_max = find_max_subarray(left_part)\n",
    "    right_sub_array, right_max = find_max_subarray(right_part)\n",
    "\n",
    "    crossing_sub_array, crossing_max = find_max_crossing_subarray(array, int(len(array)/2) - 1)\n",
    "    max_sub_array, max_sum = left_sub_array, left_max\n",
    "\n",
    "    if left_max < right_max:\n",
    "        max_sub_array, max_sum = right_sub_array, right_max\n",
    "\n",
    "    if max_sum < crossing_max:\n",
    "        max_sub_array, max_sum = crossing_sub_array, crossing_max\n",
    "\n",
    "    return max_sub_array, max_sum\n",
    "\n",
    "array_test = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]\n",
    "sub_array, max_sum = find_max_subarray(array_test)\n",
    "print(f'The max sub array is {sub_array} and the max sum is {max_sum}')\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a1ca9015",
   "metadata": {},
   "source": [
    "### 线性时间复杂度算法\n",
    "上面所示的算法的时间复杂度：T(n) = n*lg(n)\n",
    "我们可以找到时间复杂度更好的算法来解决最大子数组问题。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "51f98b9f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The max sub array is [18, 20, -7, 12] and sum is 43\n"
     ]
    }
   ],
   "source": [
    "\n",
    "def liner_find_max_subarray(array):\n",
    "    ''' 线性时间复杂度查找最大子数组 '''\n",
    "    left = 0\n",
    "    right = 0\n",
    "    max_sum = - maxsize - 1\n",
    "    sum_now = 0\n",
    "\n",
    "    i = left\n",
    "    j = right\n",
    "    while j < len(array):\n",
    "        sum_now += array[j]\n",
    "        if sum_now > max_sum:\n",
    "            max_sum = sum_now\n",
    "            left = i\n",
    "            right = j\n",
    "        if sum_now < 0:\n",
    "            sum_now = 0\n",
    "            i = j + 1\n",
    "        \n",
    "        j += 1\n",
    "    return array[left:right+1], max_sum\n",
    "\n",
    "array = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7]\n",
    "\n",
    "max_subarray, max_sum = liner_find_max_subarray(array)\n",
    "print(\"The max sub array is {0} and sum is {1}\".format(max_subarray, max_sum))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "env_py38",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.18"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
